# 406. 根据身高重建队列
# https://leetcode.cn/problems/queue-reconstruction-by-height/description/
import bisect
from typing import List


class Solution2:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: [-x[0], x[1]])
        result = []
        for p in people:
            result.insert(p[1], p)
        return result


class BIT:
    def __init__(self, n):
        self.tree = [0] * (n + 1)

    def lowbit(self, x):
        return x & (-x)

    def update(self, i, delta):
        i += 1
        while i < len(self.tree):
            self.tree[i] += delta
            i += self.lowbit(i)

    def prefix_sum(self, i):
        i += 1
        summ = 0
        while i > 0:
            summ += self.tree[i]
            i -= self.lowbit(i)
        return summ

# 树状数组
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        result = [None] * len(people)
        tree = BIT(len(people))
        people.sort()
        n = len(people)
        for i in range(n):
            tree.update(i + 1, 1)

        people.sort()
        prev = None
        count = 0
        for h, k in people:
            k_tmp = k
            if h == prev:
                k_tmp = k - count
                count += 1
            else:
                prev = h
                count = 1

            left, right = 0, len(people)
            while left < right:
                mid = (left + right) // 2
                if tree.prefix_sum(mid) < k_tmp:
                    left = mid + 1
                else:
                    right = mid

            while result[left] and tree.prefix_sum(left) == k_tmp:
                left += 1
            result[left] = [h, k]
            tree.update(left + 1, -1)
        return result


if __name__ == '__main__':
    people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
    people = [[6, 0], [5, 0], [4, 0], [3, 2], [2, 2], [1, 4]]
    print(Solution().reconstructQueue(people))
    print(Solution2().reconstructQueue(people))
